package acwing.数学.质数;

import java.util.Scanner;

/**
 * 筛质数
 *
 * @author yang
 * @date 2022/1/15
 */
public class 筛质数 {

    static int N = 100010;
    static int[] prim = new int[N];
    static boolean[] st = new boolean[N];
    static int cnt;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        getPrim(n);
        System.out.println(cnt);
    }

    /**
     * 埃算法
     * 只要筛质数的倍数就行了
     * @param n
     */
    private static void getPrim(int n) {

        for (int i = 2; i <= n; i++) {
            if (!st[i]) {
                prim[cnt++] = n;
                for (int j = i + i; j <= n; j += i) st[j] = true;
            }
        }
    }

    /**
     * 线性筛发
     * @param n
     */
    private static void getPrim1(int n) {

        for (int i = 2; i <= n; i++) {
            if (!st[i]) prim[cnt++] = i;
            for (int j = 0; prim[j] <= n / i; j++) {
                st[prim[j] * i] = true; // 用最小质因子去筛掉他
                // 因为是从小到大，所有prim[j] 一定是最小质因子
                if (i % prim[j] == 0) break;
            }
        }
    }

}
